package com.itheima.datastructure.queue;

import java.util.Iterator;

/**
 * 仅用 head, tail 判断空满, head, tail 需要换算成索引值
 *
 * @param <E> 队列中元素类型
 */
public class ArrayQueue31<E> implements Queue<E>, Iterable<E> {

    private final E[] array;
    private int head = 0; //非索引，索引值 = head % array.length
    private int tail = 0; //非索引，索引值 = tail % array.length

    @SuppressWarnings("all")
    public ArrayQueue31(int capacity) {
        //1 . 跑异常
        //2 . 找一个刚好比他大的2的n次方的容量
        int res = capacity & (capacity - 1);//==0则说明是2的n次方
        if (res != 0) {
            //找一个刚好比他大的2的n次方的容量
            int n = (int) (Math.log10(capacity - 1) / Math.log10(2)) + 1; //log2N +1
            capacity = 1 << n;
        }
        array = (E[]) new Object[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
//        array[tail % array.length] = value;
        array[tail & (array.length - 1)] = value;//需要保证array.length为2的n次方
        tail++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
//        E value = array[head % array.length];
        E value = array[head & (array.length - 1)];//需要保证array.length为2的n次方
        head++;
        return value;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
//        return array[head % array.length];
        return array[head & (array.length - 1)];//需要保证array.length为2的n次方
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    @Override
    public boolean isFull() {
        return tail - head == array.length;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;

            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public E next() {
//                E value = array[p % array.length];
                E value = array[p & (array.length - 1)]; //需要保证array.length为2的n次方
                p++;
                return value;
            }
        };
    }
}

